package Tree_09.HuffmanCode_06;

/*
 * @Author 罗
 * @date 2020/3/24 - 7:12 下午
 *
 */

import java.util.*;

public class HuffmanDecode {
    /**
     * @param huffmanCodeTable Huffman编码表
     * @param huffmanCodeBytes 要用Huffman编码表解码的数据
     */
    public static byte[] huffmanDecode(Map<Byte, String> huffmanCodeTable, byte[] huffmanCodeBytes) {

        boolean coverPosition = true;
        StringBuilder binaryStringData = new StringBuilder();
        /*
         * 1.得到huffmanCodeBytes[] 对应的 二进制字符串
         * */
        for (int i = 0; i < huffmanCodeBytes.length; i++) {
            if (i == huffmanCodeBytes.length - 1) {
                coverPosition = false;
            }
            binaryStringData.append(byteDataToString(huffmanCodeBytes[i], coverPosition));
        }

        /*System.out.println("将已编码的byte[]转为二进制字符串");
        System.out.println(binaryStringData.toString());
        */
        /*
         * 2.把字符串按照指定的huffman解码表进行解码
         */
        Map<String, Byte> huffmanDecodeTable = getHuffmanDecodeTable(huffmanCodeTable);

        /*
         * 3.将二进制字符串解码为byte[]
         * */
        Byte[] byteData = decode(huffmanDecodeTable, binaryStringData);
        /*
        System.out.println("将二进制字符串通过Huffman解码表 转为（解压）为存放ASC码的byte[]");
        System.out.println(Arrays.toString(byteData));
        */
        byte[] bytes = new byte[byteData.length];
        for (int i = 0; i < bytes.length; i++) {
            bytes[i] = byteData[i];
        }
        return bytes;
    }

    /**
     * 使用Huffman解码表将String类型的二进制数据解码为byte[]
     *
     * @param huffmanDecodeTable
     * @param binaryString
     * @return
     */
    private static Byte[] decode(Map<String, Byte> huffmanDecodeTable, StringBuilder binaryString) {

        List<Byte> byteList = new LinkedList<>();
        String singleCharacter;
        int count;
        for (int i = 0; i < binaryString.length(); ) {
            count = 1;
            while (true) {
                singleCharacter = binaryString.substring(i, i + count);
                if (huffmanDecodeTable.get(singleCharacter) != null) {
                    break;
                }
                count++;
            }
            byteList.add(huffmanDecodeTable.get(singleCharacter));
            /*
            * i+count指向了截取子字符串的end，subString(int start,int end)含头不含尾
            * 所以i的下一次起点就是i+count
            * for循环中的i++必须去掉
            * */
            i += count;
        }
        /*
         * 新建一个Byte[]用于 存放List的数组
         * 数组的类型必须和List<>的泛型一致，区分 包装类 Integer int
         * */
        Byte[] B = new Byte[byteList.size()];
        /*
         * 将List<Byte> 存储到B中，并返回B
         * */
        return byteList.toArray(B);
    }

    /**
     * 根据Huffman编码表返回Huffman解码表
     *
     * @param huffmanCodeTable
     * @return
     */
    private static Map<String, Byte> getHuffmanDecodeTable(Map<Byte, String> huffmanCodeTable) {
        /*
         * 2.把字符串按照指定的huffman解码表进行解码
         *       需要把Huffman编码表的key-value交换位置 形成 Huffman解码表
         *      (1)创建Huffman解码表
         * */
        Map<String, Byte> huffmanDecodeTable = new HashMap<>();
        /*
         * 遍历Huffman编码表
         * */
        Set<Map.Entry<Byte, String>> set = huffmanCodeTable.entrySet();
        for (Map.Entry<Byte, String> byteStringEntry : set) {
            /*
             * 将Huffman编码表的key-value交换放入Huffman解码表
             * */
            huffmanDecodeTable.put(byteStringEntry.getValue(), byteStringEntry.getKey());
        }
        return huffmanDecodeTable;
    }

    /**
     * 将byte中的数据转为二进制的字符串，全部是以补码的形式存储
     * 例如 byte[huffmanCodeBytes.length-1] = 28
     * 28 原码 1 1100 ->反码 1 1100 ->补码 1 1100
     * 补码 1 1100 最终转为二进制字符串的时候也应该是1 1100
     * 如果添加位数 0001 1100 则多出来的部分，需要到编码表中查找，最终解码出来的数据和原数据不一致
     * 编码后的字符串数组    huffmanCodeBytes[]中存储的是将编码好的二进制字符串连续的存储到huffmanCodeBytes[]数组中
     * 0 - huffmanCodeBytes.length-2 都是连续的
     * 但是huffmanCodeBytes.length-1 个元素可能没有完全塞满有效数据（比如上面的举例），解码时也应该只将有效数据拼接为二进制字符串
     *
     * @param dataByte
     * @param coverPosition 是否需要补位，如果是最后一个字节，则不能补高位
     * @return
     */
    private static String byteDataToString(byte dataByte, boolean coverPosition) {
        /*
         * 计算机中存储的数据是以补码的形式存在的
         * -1 原码 1000 0001 ->反码 1111 1110 ->补码 1111 1111
         * int 长度4子节 -> -1的int为 1111 1111 1111 1111 1111 1111 1111 1111 共为4字节
         * Integer.toBinaryString(int i)没有重载为Integer.toBinaryString(byte b)的方法
         * 转为二进制字符串的时候长度是原来的4倍，所以我们要截取字符串
         * 所以需要
         * 1.将byte转为int
         * 2.将int转为二进制字符串
         * 3.将二进制字符串截取为byte的长度
         *
         *
         * 截取字符串长度的过程中
         * 1 原码  0000 0001 ->反码 0000 0001 ->补码 0000 0001
         *  (int) 1 = 1
         * Integer.toBinaryString(1) ---> 1
         * 如果用截取负数的方法截取 1 ，会越界异常，1的总长度只为1
         * 所以我们应该把正数补位，凑够至少8位
         *      即256 -> 1 0000 0000
         * int 1 | 1 0000 0000 = 1 0000 0001
         * 就能对其进行截取最后8位的操作
         *
         * 举例 将 byte类型的 -8 转为二进制字符串
         *      负数的补码 = 反码 + 1
         *      -8 原码  1000 1000 ->反码 1111 0111 ->补码 1111 1000
         *      -8在计算机中存储的形式为 1111 1000
         * */
        int temp = dataByte;
        /*
         * 还有一种情况，当传进来的byte不足8位，但又不应该补齐的情况
         *
         * */
        if (coverPosition) {
            temp = temp | 0b1_0000_0000;
        }
        String binaryString = Integer.toBinaryString(temp);
        if (coverPosition) {
            binaryString = binaryString.substring(binaryString.length() - 8);
        }
        return binaryString;
    }
}
